package list

// 删除节点
// lsit.next = list.next.next
// 插入节点
// r.next = list.next
// list.next = r

type ListNode struct {
	Val  int
	Next *ListNode
}

func reverseList(head *ListNode) *ListNode {
	var pre *ListNode
	post := head

	for post != nil {
		temp := post.Next
		post.Next = pre
		pre = post
		post = temp
	}
	return pre
}

func reverseList2(head *ListNode) *ListNode {
	if head == nil || head.Next == nil {
		return head
	}
	cur := reverseList2(head)
	head.Next.Next = head
	head.Next = nil
	return cur
}

func removeNthFromEnd(head *ListNode, n int) *ListNode {
	p1, p2 := head, head
	// p1移动到n+1位置
	for i := 0; i < n; i++ {
		p1 = p1.Next
	}
	//如果n = len（list）则是删除整数第一个节点 直接返回head.next
	if p1 == nil {
		return head.Next
	}

	for p1.Next != nil {
		p1 = p1.Next
		p2 = p2.Next
	}
	p2.Next = p2.Next.Next
	return head
}

func swapPairs(head *ListNode) *ListNode {
	dummyHead := &ListNode{Val: 0, Next: head}
	temp := dummyHead
	for temp.Next != nil && temp.Next.Next != nil {
		node1 := temp.Next
		node2 := temp.Next.Next

		node1.Next = node2.Next
		temp.Next = node2
		node2.Next = node1
		temp = node1
	}
	return dummyHead.Next
}

// 快慢指针
func hasCycle(head *ListNode) bool {
	if head == nil || head.Next == nil {
		return false
	}
	slow := head
	fast := head.Next
	for slow != fast {
		if fast == nil || fast.Next == nil {
			return false
		}
		slow = slow.Next
		fast = fast.Next.Next
	}
	return true
}

func hasCycle2(head *ListNode) bool {
	slow := head
	fast := head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			return true
		}
	}
	return false
}

// 83
func deleteDuplicates(head *ListNode) *ListNode {
	// p := head
	// for p != nil && p.Next != nil {
	// 	if p.Next.Val == p.Val {
	// 		p.Next = p.Next.Next
	// 	} else {
	// 		p = p.Next
	// 	}
	// }
	// return head

	l, r := head, head
	for r != nil {
		curValue := l.Val
		for r != nil && r.Val != curValue {
			r = r.Next
		}
		l.Next = r
		l = r
	}
	return head
}

// 相交
func getIntersectionNode(headA, headB *ListNode) *ListNode {
	p1 := headA
	p2 := headB

	for p1 != p2 {
		if p1 != nil {
			p1 = p1.Next
		} else {
			p1 = headB
		}
		if p2 != nil {
			p2 = p2.Next
		} else {
			p2 = headA
		}
	}
	return p1
}

func removeElements(head *ListNode, val int) *ListNode {
	dummyHead := &ListNode{Val: 0, Next: head}
	p := dummyHead
	for p != nil && p.Next != nil {
		if p.Next.Val == val {
			p.Next = p.Next.Next
		}
		if p.Next != nil && p.Next.Val != val {
			p = p.Next
		}
	}
	return dummyHead.Next
}

func detectCycle(head *ListNode) *ListNode {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
		if slow == fast {
			slow = head
			for slow != fast {
				slow = slow.Next
				fast = fast.Next
			}
			return slow
		}
	}
	return nil
}
